package name.huzhenbo.java.algorithm.talent;

import name.huzhenbo.java.collection.Stack;

class Maze {
    private int[][] mazeGraph;
    Stack<Step> currentPath;

    public Maze(int[][] mazeGraph) {
        this.mazeGraph = mazeGraph;
        currentPath = new Stack<Step>();
    }

    public void go() {
        Step step = startStep();
        while (step != null) {
            // new step, or an old step (from pop up) with new next step
            if(step.notSteped() || step.next() != null) moveTo(step);
            if(hasReachDestination(step)){
                break;
            }

            if(step.next() != null){
                step = step.next();
            }else{
                step = currentPath.pop();
            }
        }

        footPrint(currentPath);
    }

    private boolean hasReachDestination(Step step) {
        return step.x == mazeGraph.length - 2 && step.y == mazeGraph[0].length - 2;
    }

    private Step startStep() {
        return new Step(1, 1);
    }

    private void footPrint(Stack<Step> path) {
        for(Step step : path.getList()){
            step.footPrint();
        }
    }

    private void moveTo(Step step) {
        mazeGraph[step.x][step.y] = 1;
        currentPath.push(step);
    }

    private class Step {
        private int x;
        private int y;

        public Step(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Step next() {
            if (east() != null) {
                return east();
            } else if (south() != null) {
                return south();
            } else if (west() != null) {
                return west();
            } else if (north() != null) {
                return north();
            }
            return null;
        }

        private Step north() {
            return mazeGraph[x - 1][y] == 0 ? new Step(x - 1, y) : null;
        }

        private Step west() {
            return mazeGraph[x][y - 1] == 0 ? new Step(x, y - 1) : null;
        }

        private Step south() {
            return mazeGraph[x + 1][y] == 0 ? new Step(x + 1, y) : null;
        }

        private Step east() {
            return mazeGraph[x][y + 1] == 0 ? new Step(x, y + 1) : null;
        }

        public void footPrint() {
            System.out.println("Point:" + new Integer(x).toString() + "." + new Integer(y).toString());
        }

        public boolean notSteped() {
            return mazeGraph[x][y] == 0;
        }
    }
}
